package LeetCode;

import java.util.HashMap;
import java.util.Random;

public class LC_380_InsertDeleteGetRandomO1 {

    public static void main(String[] args) {

    }


    public class RandomizedSet {

        HashMap<Integer, Integer> map1;
        HashMap<Integer, Integer> map2;
        Random rand;

        public RandomizedSet() {
            map1 = new HashMap<>();
            map2 = new HashMap<>();
            rand = new Random(System.currentTimeMillis());
        }

        public boolean insert(int val) {
            if (map1.containsKey(val)) return false;
            else {
                map1.put(val, map1.size());
                map2.put(map2.size(), val);
            }
            return true;
        }

        public boolean remove(int val) {
            if (map1.containsKey(val)) {
                int index = map1.get(val);
                map1.remove(val);
                map2.remove(index);
                if (map1.size() == 0)
                    return true;
                if (index == map1.size())
                    return true;
                int key1 = map2.get(map2.size());
                map1.put(key1, index);
                map2.remove(map2.size());
                map2.put(index, key1);
            } else
                return false;
            return true;
        }

        public int getRandom() {
            if (map1.size() == 0) return -1;
            if (map1.size() == 1) return map2.get(0);
            return map2.get(new Random().nextInt(map1.size()));
        }

    }
}